package pwd.allen;

/**
 * 归并排序
 * 原理：采用分治法，先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
 *
 * 时间复杂度：
 *  平均：O(nlog2n) 最坏：O(nlog2n) 最好：O(nlog2n)
 * 空间复杂度：O(n)
 * 稳定性：稳定
 */
public class MergingSort {

    public void sortMerging(int[] array) {
        sort(array, 0, array.length - 1);
    }

    private void sort(int[] array, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            sort(array, left, middle);
            sort(array, middle + 1, right);
            merge(array, left, middle, right);
        }

    }

    private void merge(int[] array, int left, int center, int right) {
        // 临时缓存数组
        int[] temp = new int[right - left + 1];
        int first = left;
        int second = center + 1;
        int index = 0;
        // 比较并合并两个有序数组到临时数组，直到有一个数组遍历完为止
        while (first <= center && second <= right) {
            if (array[first] <= array[second]) {
                temp[index++] = array[first++];
            } else {
                temp[index++] = array[second++];
            }
        }
        while (first <= center) {
            temp[index++] = array[first++];
        }
        while (second <= right) {
            temp[index++] = array[second++];
        }
        // 结果复制到到原数组
        for (int i = 0; i < temp.length; i++) {
            array[left + i] = temp[i];
        }
    }

}
